/*
Date:20210420 0：09
key:一维dp，对于每个子状态只有两个选择，dp[i-1]+当前，以当前为起点，挑一个最大的。
    这个子状态表示的是从上一个未知起点到i的最大总和。而不是从开头。
    以第 i 个数"结尾"的「连续子数组的最大和」
*/
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
    //定义dp[i]是直到i的最大子序和
    vector<int>dp;
    dp.resize(nums.size());
    int max1;
    for(int i=0;i<nums.size();i++)
    {
        if(i==0){dp[i]=nums[i]; max1=dp[0];}
        else
        {
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            if(max1<dp[i])
            {max1=dp[i];}
        }
    }

    return max1;
    }
};